package com.github.yangyishe.p100;

import com.github.yangyishe.ListNode;

/**
 * 19. 删除链表的倒数第 N 个结点
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 *
 *
 * 提示：
 *
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 *
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 */
public class Problem19 {
    public static void main(String[] args) {
        int[] arr=new int[]{1,2};
        ListNode head = ListNode.getInstance(arr);
        int n=1;

        Problem19 problem19 = new Problem19();
        ListNode listNode = problem19.removeNthFromEnd(head, n);
        listNode.print();
    }

    /**
     * 思路:
     * 创建一个长度为n+1的数组, 每遍历一个元素则记录一个, 并循环式的记录在数组中. 相当于一个循环链表一样的作用.
     * 遍历到最后, 删除的元素就是当前访问元素的offset+2(如果有的话)
     * 删除方法, 就是让offset+1的元素next直接等于offset+3
     *
     * 需要考虑边界情况:
     * 1. 如果待删除元素在第一个, 则offset+1=null, 直接返回offset+3或head.next;
     * 2. 其他代码正常处理即可
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode[] lastEles=new ListNode[n+1];
        int offset=0;

        ListNode temp=head;
        while(temp!=null){
            lastEles[offset]=temp;
            offset++;
            if(offset==n+1){
                offset=0;
            }

            temp=temp.next;
        }
        // 注: offset-1存放的才是最后一个元素

        ListNode ele2RmLast=lastEles[(offset)%(n+1)];
        ListNode ele2Rm=lastEles[(offset+1)%(n+1)];
        if(ele2RmLast==null){
            return head.next;
        }else{
            ele2RmLast.next=ele2Rm.next;
            return head;
        }



    }
}
